package algorithm.t202111;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/2 9:23
 * @description :6道
 * 勇敢的心。
 * persevere to last
 * 2021.11.2
 * 李红磊
 */
public class t20211102 {

    //237.删除链表的中间节点
    public void deleteNode(ListNode node) {
        int nextVal = node.next.val;

        node.val = nextVal;

        node.next = node.next.next;


    }

    //47.全排列
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        boolean[] visit = new boolean[nums.length];

        Arrays.sort(nums);
        backTrack1(0, nums, visit, res, new ArrayList<Integer>());

        return res;

    }

    /**
     * @Author 李红磊
     * @Date 2021/11/2 9:33
     * @param: i 当前检索到的下标
     * @param: nums 目标数组
     * @param: visit 备忘录
     * @param: res 用于返回
     * @param: cur 当前的路径
     **/
    private void backTrack1(int i, int[] nums, boolean[] visit, List<List<Integer>> res, ArrayList<Integer> cur) {
        if (cur.size() == nums.length) {
            res.add(new ArrayList<>(cur));
            return;
        }

        for (int j = 0; j < nums.length; j++) {
            //剪枝
            if (j > 0 && nums[j - 1] == nums[j] && !visit[j - 1]) {
                continue;
            }

            if (!visit[j]) {
                visit[j] = true;
                cur.add(nums[j]);
                backTrack1(i + 1, nums, visit, res, cur);
                visit[j] = false;
                cur.remove(cur.size() - 1);
            }


        }


    }


    //39.组合总数
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        if (target < 0) {
            return res;
        }

        backTrack2(candidates, target, 0, new ArrayList<Integer>(), res);
        return res;

    }

    /**
     * @Author 李红磊
     * @Date 2021/11/2 14:48
     * @param: candidates 目标数组
     * @param: target 目标值
     * @param: index 当前准备取的元素的下标
     * @param: res
     **/
    private void backTrack2(int[] candidates, int target, int index, ArrayList<Integer> path, ArrayList<List<Integer>> res) {
        if (target < 0) {
            return;
        }

        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        //开始添加元素
        for (int i = index; i < candidates.length; i++) {
            path.add(candidates[i]);
            backTrack2(candidates, target - candidates[i], i, path, res);
            path.remove(path.size() - 1);

        }

    }

    //40.组合总数 ||
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);

        backTrack3(0, candidates, target, new ArrayDeque<>(), res);
        return res;

    }

    private void backTrack3(int index, int[] candidates, int target, Deque<Integer> path, ArrayList<List<Integer>> res) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if (target - candidates[i] < 0) {
                return;
            }

            if (i > index && candidates[i - 1] == candidates[i]) {
                continue;
            }

            path.addLast(candidates[i]);
            backTrack3(i + 1, candidates, target - candidates[i], path, res);
            path.removeLast();

        }

    }


    //面试题10.01 合并排序的数组
    public void merge(int[] A, int m, int[] B, int n) {
        int len_a = A.length;
        if (len_a == m && n != 0) {
            return;
        }

        int capacity = len_a - m;
        if (capacity < n) {
            return;
        }
        for (int i = 0, j = m; i < B.length && m < A.length; i++, j++) {
            A[j] = B[i];
        }

        Arrays.sort(A);

    }

    //面试题10.02 变位词组
    public List<List<String>> groupAnagrams(String[] strs) {
        ArrayList<List<String>> res = new ArrayList<>();
        HashMap<String, List<String>> map = new HashMap<>();


        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key,list);

        }

        for (String element:map.keySet()){
            res.add(map.get(element));
        }


        return res;
    }




    public static void main(String[] args) {
        t20211102 t20211102 = new t20211102();
        List<List<String>> lists = t20211102.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});

        for (List<String> list : lists) {
            for (String s : list) {
                System.out.print(s+"\t");
            }
            System.out.println();
        }


    }


}
